package com.ting.test.algorithms.滑动窗口;

import java.util.Stack;

/**
 * Created by 雷霆 on 2020/11/6.
 * <p>
 * Description：
 * 给定一个只包含正数的数组arr，arr中任何一个子数组sub，
 * 一定都可以算出(sub累加和 )* (sub中的最小值)是什么，
 * 那么所有子数组中，这个值最大是多少？
 */
public class Class2 {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 5, 4, 3, 3, 6, 7};
        int result = printMin(arr);
        System.out.println(result);
//        for (int res : result) {
//            System.out.println(res);
//        }
    }

    private static Integer printMin(int[] arr) {
        if (null == arr || arr.length < 1) {
            return null;
        }
        int length = arr.length;
        int R = 0, L = 0;
        //单调栈结构 stack 中维护一个从小到大的单调栈
        Stack<Integer> windows = new Stack<>();
        //sumList用于存储以0位置为L，0~length-1位置为R的每个子数组中元素的累加和
        int[] sumList = new int[arr.length];

        int sum = 0;
        for (int index = 0; index < length; index++) {
            sum += arr[index];
            sumList[index] = sum;

        }

        int subSum = 0;
        for (int index = 0; index < length; index++) {
            R = index;
            L = index;
            //获取当前index的R边界
            while (R < length - 1 && arr[R] >= arr[index]) {
                R++;
            }
            //获取当前index的L边界
            while (L > 0 && arr[L] >= arr[index]) {
                L--;
            }
            //计算出当前index所在的sub累加和
            subSum = (sumList[R] - sumList[L]) * index;
            while (!windows.isEmpty() && subSum >= windows.peek()) {
                windows.pop();
            }
            windows.push(subSum);

        }
        return windows.firstElement();
    }


}
